Akinori KAWACHI Kenichi KAWANO Francois LE GALL Suguru TAMAKI
Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using $lceil{sqrt{6} heta_{ m cover}^{-1}} ceil$ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of $U_1^dagger {U_2}$, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least $lceil{rac{2}{3 heta_{ m cover}}} ceil$ queries under uniform distribution over S.
This paper provides an overview on the recent research on networked control with an emphasis on the tight relation between the two fields of control and communication. In particular, we present several results focusing on data rate constraints in networked control systems, which can be modeled as quantization of control-related signals. The motivation is to reduce the amount of data rate as much as possible in obtaining control objectives such as stabilization and control performance under certain measures. We also discuss some approaches towards control problems based on techniques from signal processing and information theory.
Navrati SAXENA Abhishek ROY Jeong-Jae WON
Continuous processing and servicing of a new incoming session in LTE systems demands optimal tracking of the mobile user. In this letter, an optimal, information-theoretic framework is developed for tracking area update for next-generation LTE cellular systems. Shannon's entropy is used to characterize the location uncertainty of mobile user. The framework captures users' mobility patterns online and performs profile-based paging for optimizing the tracking area update cost. Simulation results demonstrate reductions in both update and paging costs in comparison to existing LTE systems.
Abhishek ROY Navrati SAXENA Jitae SHIN
An information-theoretic, optimal framework is developed for tracking the residents in a Context-aware Heterogenous Smart Environment. The resident-tracking problem is formulated in terms of weighted entropy. The framework provides an optimal, online learning and prediction of users movement, location as well as most probable path segments from the symbolic domain. Successful prediction helps in on-demand operations of automated indoor devices along the users future paths and locations, thus providing the necessary comfort at a near-optimal cost. Simulation results corroborate the high prediction success, thereby providing resident-comfort while reducing energy consumption and manual operations.
In this paper, we present a learning approach, positive correlation learning (PCL), that creates a multilayer neural network with good generalization ability. A correlation function is added to the standard error function of back propagation learning, and the error function is minimized by a steepest-descent method. During training, all the unnecessary units in the hidden layer are correlated with necessary ones in a positive sense. PCL can therefore create positively correlated activities of hidden units in response to input patterns. We show that PCL can reduce the information on the input patterns and decay the weights, which lead to improved generalization ability. Here, the information is defined with respect to hidden unit activity since the hidden unit plays a crucial role in storing the information on the input patterns. That is, as previously proposed, the information is defined by the difference between the uncertainty of the hidden unit at the initial stage of learning and the uncertainty of the hidden unit at the final stage of learning. After deriving new weight update rules for the PCL, we applied this method to several standard benchmark classification problems such as breast cancer, diabetes and glass identification problems. Experimental results confirmed that the PCL produces positively correlated hidden units and reduces significantly the amount of information, resulting improved generalization ability.
Shiping DUAN Youyun XU Wentao SONG
Multiuser diversity, identified by recent information theoretic results, is a form of diversity inherent in a wireless network. The diversity gain is obtained from independent time-varying fading channels across different users. The main practical issue in multiuser diversity is lack of Quality of Service (QoS) guarantees. This study proposes a wireless scheduling algorithm named MUDSEQ for downlink channels exploiting multiuser diversity under explicit QoS constraints. The numerical results demonstrate that the novel algorithm can yield non-negligible diversity gain even under tight QoS constraints and little scattering or slow fading environments. Additionally, a system framework for dynamic resource allocation based on the proposed algorithm is developed.
Taku NOGUCHI Takahiro MATSUDA Miki YAMAMOTO
Multicast transmission, which can send the same information simultaneously to multiple users, is a key technology in content delivery networks. In this paper, we discuss a new multicast architecture with network coding proposed by Li et al. , which breaks limitation of existing IP multicast in terms of network resource utilization. Network coding based multicast can achieve the max-flow, which is the theoretical upper bound of network resource utilization. However, the max-flow transmission is not always effective and may not be robust against congestion because it maximally uses link capacity of multicast distribution tree. In this paper, we first introduce a load balancing method of network coding as an alternative use to the max-flow transmission. Next, we study the feasibility of network coding based multicast architecture from performance aspect and evaluate the network coding in terms of the max-flow and load balancing with a computer simulation. There has been no evaluation of network coding in practical network environment with packet losses and propagation delay. We also describe required key techniques and technical problems to implement network coding on the current IP networks. Our results will offer valuable insight for designing the future Internet with higher and more effective network utilization.
We study the optimal transmission strategy of a multiple-input multiple-output (MIMO) communication system with covariance feedback. We assume that the receiver has perfect channel state information while the transmitter knows only the channel covariance matrix. We consider the common downlink transmission model where the base station is un-obstructed while the mobile station is surrounded by local scatterer. Therefore the channel matrix is modeled with Gaussian complex random entries with independent identically distributed rows and correlated columns. For this transmission scenario the capacity achieving eigenvectors of the transmit covariance matrix are known. The capacity achieving eigenvalues can not be computed easily. We analyze the optimal transmission strategy as a function of the transmit power. A MIMO system using only one eigenvalue performs beamforming. We derive a necessary and sufficient condition for when beamforming achieves capacity. The theoretical results are illustrated by numerical simulations.
Toshihiro IWAMOTO Yasuhiko JIMBO Kazuyuki AIHARA
We propose a novel method for analysis of time-related neuronal activities. This method can be used for the detection of firing patterns in the presence of noise, which is inevitable in physiological experiments. This method is also useful for probability density estimation, because it enables precise information quantification from a small amount of data.
The capacity of quantum channel with product input states was formulated by the quantum coding theorem. However, whether entangled input states can enhance the quantum channel is still open. It turns out that this problem is reduced to a special case of the more general problem whether the capacity of product quantum channel exhibits additivity. In the present study, we apply one of the quantum Arimoto-Blahut type algorithms to the latter problem. The results suggest that the additivity of product quantum channel capacity always holds and that entangled input states cannot enhance the quantum channel capacity.
Shogo USAMI Tsuyoshi Sasaki USUDA Ichi TAKUMI Masayasu HATA
Recently, the quantum information theory attracts much attention. In quantum information theory, the existence of superadditivity in capacity of a quantum channel was foreseen conventionally. So far, some examples of codes which show the superadditivity in capacity have been clarified. However in present stage, characteristics of superadditivity are not still clear up enough. The reason is as follows. All examples were shown by calculating the mutual information by quantum combined measurement, so that one had to solve the eigenvalue and the eigenvector problems. In this paper, we construct a simplification algorithm to calculate the mutual information by using square-root measurement as decoding process of quantum combined measurement. The eigenvalue and the eigenvector problems are avoided in the algorithm by using group covariancy of binary linear codes. Moreover, we derive the analytical solution of the mutual information for parity check codes with any length as an example of applying the simplification algorithm.
Kazunori MATSUMOTO Kazuo HASHIMOTO
Call tracking data contains a calling address, called address, service type, and other useful attributes to predict a customer's calling activity. Call tracking data is becoming a target of data mining for telecommunication carriers. Conventional data-mining programs control the number of association rules found with two types of thresholds (minimum confidence and minimum support), however, often they generate too many association rules because of the wide variety of patterns found in call tracking data. This paper proposes a new method to reduce the number of generated rules. The method proposed tests each generated rule based on Akaike Information Criteria (AIC) without using conventional thresholds. Experiments with artificial call tracking data show the high performance of the proposed method.
In this paper, we show an entropy-based approach to the privacy of multi-party protocols. First, we formulate the amount of leaked information by using mutual information for a two-party case. This is a better measure for some situations than the combinatorial measure known so far. Next, we apply multi-terminal information theoty to more than two parties and give the first formulation of the leaked information for more than two parties.
This paper suggests modified LZSS which is suitable for compressing Hangul data by Hangul character token and the string token with small size based on Hangul properties. The Hangul properties can be described in 2 ways. 1) The structure of a Hangul character consists of 3 letters: The first sound letter, the middle sound letter, and the last sound letter which are called Cho-seong, Jung-seong, and Jong-seong, respectively. 2) The code of Hangul is represented by 2 bytes. The first property is used for making the character token processing Hangul characters which occupies most of the unmatched characters. That is, the unmatched Hangul characters are replaced with one Hangul character token represented by Huffman codes of Cho-seong, Jung-seong, and Jong-seong in regular sequence, instead of 2 character tokens. The second property is used to shorten the size of the string token processing matched string. In other words, since more than 75% of Hangul data are Hangul and Hangul codes are constructed in 2 bytes, the addresses of the window of LZSS can be assigned in 2-byte unit. As a result, the distance field and the length field of the string token can be lessened by one bit each. After compressing Hangul data through these tokens, about 3% of improvement could be made in compression ratio.
This paper deals with the information leakage measurement in a distributed computation protocol called SASC. The SASC protocol is a kind of two-party protocol between a client and a server. The computation for RSA cryptosystem is the target of this paper. This paper shows that a secure RSA-SASC protocol proposed recently could be changed to be insecure if the client which has secret information were to complain about the computation result. This paper first clarifies how to measure the information amount which leaks through the protocol. It, then, shows an attack procedure to make use of the client's complaint. Effectiveness of the attack procedure is measured by the information theoretic measure. By using the same measure, it is shown that some attacks do not work to derive the client's secret. It is also shown that a practical countermeasure to limit the number of incorrect computation allowed is effctive to limit the leakage of the secret information to some reasonable extent.
In the band-limited signal space, the mutual relation between continuous time signal and discrete time signal is expressed by the sampling theorem of Whittaker-Someya-Shannon. This theorem consists of an orthonormal expansion formula using sinc functions. In that formula, the expansion coefficients are identical to the sample values of signals. In general, the bandlimited signal space is not always suited to model the signals in nature. The authors have proposed a new model for signal processing based on finite times continuously differentiable functions. This paper aims to complete the sampling theorem for the spline signal spaces, which corresponds to the sampling theorem of Whittaker-Someya-Shannon in the band-limited signal space. Since the obtained sampling theorem gives the simplest representation of signals, it is considered to be the most fundamental characterization of spline functions used for signal processing. The biorthonormal basis derived in this paper is considered to be a system of delta functions at sampling points with some continuous differentiability.
Hui ZHAO Toru SATO Iwane KIMURA
This paper presents an adaptive rate error control scheme for digital communication over time-varying channels. The cyclic code with majority-logic decoding is used in a cascaded way as an inner code to create a simple and powerful hybrid-ARQ error control scheme. Inner code is used only for error correction and the outer code is used for both error correction and error detection. When an error is detected, retransmission is required. The unsuccessful packets are not discarded as with conventional schemes, but are combined with their retransmitted copies. Approximations for the throughput efficiency and the undetectable error probability are given. A high reliability coupled with a simple high-speed implementation makes it suitable for high data rate error control over both stationary and nonstationary channels. Adaptive error control scheme becomes the best solution for time-varying channels when the optimum code is selected according to the actual channel conditions to enhance the system performance. The main feature of this system is that the basic structure of the encoder and decoder need not be modified while the error-correction capability of the code increases. Results of a comparative analysis show that the proposed scheme outperforms other similar ARQ protocols.
Farokh MARVASTI Mohammed NAFIE
Redundancy is introduced by sampling a bandlimited signal at a higher rate than the Nyquist rate. In the cases of erasures due to fading or jamming, the samples are discarded. Therefore, what we get at the output of the receiver is a set if nonuniform samples obtained from a uniform sampling process with missing samples. As long as the rate of nonuniform samples is higher than the Nyquist rate, the original signal can be recovered with no errors. The sampling theorem can be shown to be equivalent to the fundamental theorem of information theory. This oversampling technique is also equivalent to a convolutional code of infinite constraint length is the Field of real numbers. A DSP implementation of this technique is through the use of a Discrete Fourier Transform (DFT), which happens to be equivalent to block codes in the field of real numbers. An iterative decoder has been proposed for erasure and impulsive noise, which also works with moderate amount of additive random noise. The iterative method is very simple and efficient consisting of modules of Fast Fourier Transforms (FFT) and Inverse FFT's. We also suggest a non-linear iterative method which converges faster than the successive approximation. This iterative decoder can be implemented in a feedback configuration. Besides FFT, other discrete transforms such as Discrete Cosine Transform, Discrete Sine Transform, Discrete Hartley Transform, and Discrete Wavelet Transform are used. The results are comparable to FFT with the advantage of working in the field of real numbers.
Masayuki ARIYOSHI Takaya YAMAZATO Iwao SASASE Shinsaku MORI
In conventional trellis coded modulation (TCM), a bit rate of m/m+1 convolutional encoder is employed for n information bits (mn), where 2n+1 signal points are required. In this paper, we propose a novel TCM system using totally overlapped signal sets (TO-TCM), i.e., each signal point is used twice. Thus, TO-TCM can realize only half signal points (2n) comparing with those of a conventional TCM system (2n+1), and it is possible to implement a coded modulation system without doubling the signal points by an insertion of redundant bits. The cases of the proposed schemes which have a process to extend the minimum free distances between the signal points can achieve a considerable coding gain in comparison to the traditional uncoded systems with 2n signal points. Moreover, as the proposed scheme needs only half signal points (2n) of those of conventional TCM, the average power is lower and it is less sensitive to the carrier phase offset.
Kiyomichi ARAKI Masayuki TAKADA Masakatu MORII
In this paper a recursive form of Welch-Berlekamp (W-B) algorithm is provided which is a novel and fast decoding algorithm.